//给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。 
//
// 换句话说，s1 的排列之一是 s2 的 子串 。 
//
// 
//
// 示例 1： 
//
// 
//输入：s1 = "ab" s2 = "eidbaooo"
//输出：true
//解释：s2 包含 s1 的排列之一 ("ba").
// 
//
// 示例 2： 
//
// 
//输入：s1= "ab" s2 = "eidboaoo"
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s1.length, s2.length <= 104 
// s1 和 s2 仅包含小写字母 
// 
// Related Topics 哈希表 双指针 字符串 滑动窗口 
// 👍 458 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
func checkInclusion(s1 string, s2 string) bool {

    need, window := make(map[byte]int), make(map[byte]int)

    for i := range s1 {
        need[s1[i]]++
    }

    matchNum := 0

    left, right := 0, 0

    for right < len(s2) {
        v2 := s2[right]
        right++

        if _, ok := need[v2]; ok {
            window[v2]++

            if window[v2] == need[v2] {
                matchNum++
            }
        }

        // 缩小情况
        for right - left == len(s1) {
            if len(need) == matchNum {
                return true
            }

            v1 := s2[left]
            left++

            if _, ok := need[v1]; ok {
                if window[v1] == need[v1] {
                    matchNum--
                }

                window[v1]--
            }
        }

    }

    return false
}
//leetcode submit region end(Prohibit modification and deletion)
